package cn.corffen.test.algorithm.string;

public class PatternMatch {
    int R = 256;
    int[][] dfa;
    int  M ;

    public PatternMatch(String pattern){
         M = pattern.length();
        dfa = new int[R][M];
        dfa[pattern.charAt(0)][0] = 1;
        for (int X = 0,j = 1; j < M; j++) {
            for (int c = 0; c < R; c++) {
                dfa[c][j]= dfa[c][X];
            }
            dfa[pattern.charAt(j)][j] = j+1;
            X = dfa[pattern.charAt(j)][X];
        }
    }

    public int kmpForDfa(String text){
        int j = 0;
        int i = 0;
        for (int N = text.length() ; i < N && j<M; i++) {
            j = dfa[i][j];
        }
        if (j == M) {
            return i-M;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println("使用BF算法");
        System.out.println("查找ba的位置:" + BF("aaaaba", "ba"));
        System.out.println("查找abcac的位置:" + BF("ababcabcacbab", "abcac"));
    }

    public static int BF(String s, String t) {
        int n = s.length();
        int m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j = 0;
                i = i - j + 1;
            }
        }

        if (j == m) {
            return i - m;
        }
        return -1;
    }

    /**
     * KMP算法
     *
     * @return
     */
    public int kmp(String source, String pattern) {
        int i = 0, j = 0;
        char[] src = source.toCharArray();
        char[] ptn = pattern.toCharArray();
        int sLen = src.length;
        int pLen = ptn.length;
        int[] next = getNext(ptn);
        while (i < sLen && j < pLen) {
            // 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
            if (j == -1 || src[i] == ptn[j]) {
                i++;
                j++;
            } else {
                // 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
                j = next[j];
            }
        }
        if (j == pLen)
            return i - j;
        return -1;
    }

    /**
     * next[j] = k 的意思是当s[i]!=p[j]时,p需要回退到第k个元素与s[i]进行匹配
     * 这时模式串中的j-1之前的元素必然有 p[1,2,...j-1] 与s[i-1之前的元素相等],0<=k<=j
     * 也就是 有p[j-k+1,j-k+2,...j-1]=s[i-k+1,s-k+2,...i-1]
     * 而next[j] = k,则有  p[1,2,...k-1] k-1个元素与 s[i-k+1,s-k+2,...i-1] k-1个元素相等
     *
     * 上面两式子相等 就有了 p[1,2...k-1] = p[j-k+1,j-k+2,...j-1]
     * 这个等式与主串无关的,而next[0] = -1 ,next[j] = k,
     * 再利用上面推出来的公式 ,计算next[j+1]
     * 那么就可以得到next数组的所有值了
     * @param p
     * @return
     */
    public int[] getNext(char[] p) {
        // 已知next[j] = k,利用递归的思想求出next[j+1]的值
        // 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
        // 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
        // 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
        // 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
        int pLen = p.length;
        int[] next = new int[pLen];
        int k = -1;
        int j = 0;
        next[0] = -1; // next数组中next[0]为-1
        while (j < pLen - 1) {
            //k==-1 表示当前next数组中没有匹配的,需要将主串与子串都往后移一位
            //如果第k位的字符刚好与第j位的字符也匹配上了,同样需要将主串与子串都往后移一位
            //同时令next[j] = k;
            if (k == -1 || p[j] == p[k]) {
                k++;
                j++;
                next[j] = k;
            } else {
                //如果第k位的字符与第j位的字符不相等, 就令k = next[k].继续下一次的循环
                k = next[k];
            }
        }
        return next;
    }

    protected int[] getNext2(char[] p) {
        // 已知next[j] = k,利用递归的思想求出next[j+1]的值
        // 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
        // 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
        // 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
        // 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
        int pLen = p.length;
        int[] next = new int[pLen];
        int k = -1;//数组next对应的值,第一位是-1,表示第一位就不匹配的话,就完后移动一步,继续下一次的比较
        int j = 0;//数组next的索引
        next[0] = -1; // next数组中next[0]为-1
        while (j < pLen - 1) {
            //k==-1 表示当前next数组中没有匹配的,需要将主串与子串都往后移一位
            //如果第k位的字符刚好与第j位的字符也匹配上了,同样需要将主串与子串都往后移一位
            //同时令next[j] = k;
            if (k == -1 || p[j] == p[k]) {
                k++;
                j++;
                if (p[j] != p[k]) {
                    next[j] = k;
                }else {
                    next[j] = next[k];
                }
            } else {
                //如果第k位的字符与第j位的字符不相等, 就令k = next[k].继续下一次的循环
                k = next[k];
            }
        }
        return next;
    }
}
